{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Encode N-ary Tree to Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #design #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #设计 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: CodecDriver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将 N 叉树编码为二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设计一个算法，可以将 N 叉树编码为二叉树，并能将该二叉树解码为原 N 叉树。一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。类似地，一个二叉树是指每个节点都有不超过 2 个孩子节点的有根树。你的编码 / 解码的算法的实现没有限制，你只需要保证一个 N 叉树可以编码为二叉树且该二叉树可以解码回原始 N 叉树即可。</p>\n",
    "\n",
    "<p>例如，你可以将下面的 <code>3-叉</code> 树以该种方式编码：</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/12/narytreebinarytreeexample.png\" style=\"width: 500px;\"></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意，上面的方法仅仅是一个例子，可能可行也可能不可行。你没有必要遵循这种形式转化，你可以自己创造和实现不同的方法。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>N</code>&nbsp;的范围在 <code>[1, 1000]</code></li>\n",
    "\t<li>不要使用类成员 / 全局变量 / 静态变量来存储状态。你的编码和解码算法应是无状态的。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [encode-n-ary-tree-to-binary-tree](https://leetcode.cn/problems/encode-n-ary-tree-to-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [encode-n-ary-tree-to-binary-tree](https://leetcode.cn/problems/encode-n-ary-tree-to-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,3,2,4,null,5,6]', '[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### 官1：非ascii字符来识别字符为空的情况(unichr函数，python3废弃--无法调试成功)\n",
    "# class Codec:\n",
    "#     def encode(self, strs):\n",
    "#         \"\"\"Encodes a list of strings to a single string.\n",
    "#         :type strs: List[str]\n",
    "#         :rtype: str\n",
    "#         \"\"\"\n",
    "#         if len(strs) == 0: \n",
    "#             # return unichr(258) ### python-2 有unichr函数\n",
    "#             return chr(258)\n",
    "        \n",
    "#         # encode here is a workaround to fix BE CodecDriver error\n",
    "#         # return unichr(257).join(x.encode('utf-8') for x in strs)\n",
    "#         return chr(257).join(x.encode('utf-8') for x in strs)\n",
    "        \n",
    "\n",
    "#     def decode(self, s):\n",
    "#         \"\"\"Decodes a single string to a list of strings.\n",
    "#         :type s: str\n",
    "#         :rtype: List[str]\n",
    "#         \"\"\"\n",
    "#         # if s == unichr(258): \n",
    "#         #     return []\n",
    "#         # return s.split(unichr(257))\n",
    "\n",
    "#         if s==chr(258):return []\n",
    "#         return s.split(chr(257))\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))\n",
    "\n",
    "# 官1：网友py3版\n",
    "class Codec:\n",
    "    def encode(self,strs):\n",
    "        if len(strs)==0:\n",
    "            return chr(258)\n",
    "\n",
    "        return chr(257).join(strs)\n",
    "\n",
    "    def decode(self,s):\n",
    "        if s==chr(258): return []\n",
    "        return s.split(chr(257))\n",
    "\n",
    "# 官2：基于http1.1使用的编码，不依赖与输入字符集\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def encode(self, strs):\n",
    "        \"\"\"Encodes a list of strings to a single string.\n",
    "        :type strs: List[str]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(strs) == 0: \n",
    "            return chr(258)\n",
    "        \n",
    "        # encode here is a workaround to fix BE CodecDriver error\n",
    "        return chr(257).join(strs)\n",
    "        \n",
    "\n",
    "    def decode(self, s):\n",
    "        \"\"\"Decodes a single string to a list of strings.\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        if s == chr(258): \n",
    "            return []\n",
    "        return s.split(chr(257))\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.decode(codec.encode(strs))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
